This invention is generally related to the field of Electronic Design Automation as it applies to the design of semiconductor chips and, more generally, to a method for placing cells in a VLSI chip and legalizing the process with a minimal amount of disturbance to the cell placement.
Typical stages in an integrated circuit (i.e., IC's or VLSI chips) design flow include logic synthesis, floorplanning, placement, routing and timing analysis steps. The placement phase of physical design is of paramount importance given the impact of placement solution on design metrics like area, routability and timing. The cell placement problem is among the most fundamental in VLSI physical design and has been extensively researched over the past two decades. In the context of standard cells, the classical wire-length driven formulation can be stated as follows: given a netlist of standard cells, each component is assigned to a row and to an x-position in that row such that no two cells overlap and that the estimated wire length is minimized.
Placement techniques can be broadly classified as:    1) partitioning-based methods as described, e.g., in the article “Min-cut Placement” by M. A. Breuer, published in the Proc. of IEEE Design Automation and Fault-Tolerant Computing, pp. 343–382, October 1977, and in the article “Efficient network flow based min cut balanced partitioning,” H. Yang and D. F. Wong, published in the Proceedings of the IEEE/ACM Int. Conf. Computer-Aided Design, pp. 50–55, 1994.    (2) analytical placement methods, as described in the article “Generic Global Placement and Floorplanning,” by H. Eisenmann and F. M. Johannes, published in the Proceedings of IEEE/ACM Design Automation Conference, pp. 269–274, 1998; and    (3) annealing-based methods, as described in the article “Efficient and Effective Placement for Very Large Circuits,” by W-J. Sun and C. Sechen, published in the IEEE Transactions on Computer-Aided Design, pp. 349–359, 1995.
Most top-down large-scale placement techniques (like partitioning and analytical methods) divide the placement stage into global and detailed placement phases. The global placement phase assigns cells to global bins in a grid imposed over the layout area, and thereby decides the global ordering of cells. The detailed placement phase determines the exact cell locations through local perturbations to minimize a desired objective function.
Placement legalization specifically involves resolving overlaps in cell placement during the physical design phase. In general, placement legalization is a required step in several placement approaches to arrive at a valid overlap-free placement that satisfies design rule constraints. The input to the legalization phase is an overlapping placement configuration and the desired output is an overlap-free placement with minimal perturbation to cell locations. Overlap-removal techniques can be used within the context of both global and detailed placement algorithms that generate intermediate overlapping cell placement solutions requiring coarse or fine legal assignment.
Placement legalization is also vital in the context of physical synthesis, wherein the logic/netlist is changed to correct timing violations that invariably result in cell overlaps. In this scenario, it is desirable that any given cell does not move a large distance from the current location to find a legal placement slot, thereby minimizing the impact on the final timing results. The strength of the overall approach to correct timing through synthesis and placement transforms depends on the placement legalization technique that can effectively realize the solutions with minimal placement changes. Other physical design applications requiring an Engineering Change Order (ECO) facility from placement tools also benefit from such techniques that legalize the placement.
The method presented in the invention directly addresses such overlap-removal techniques.
Terminology:
Some standard terminology and definitions from literature are presented for clarity of content and to be utilized hereinafter:
Graph: A graph G=(V, E) consists of a set of objects V={ν1, ν2 . . . } called vertices (or nodes), and another set E={e1, e2 . . . }, whose elements are called edges, such that each edge ek is identified with an unordered pair (νi, νj) of vertices. The vertices νi, νj associated with edge ek are called the end vertices of ek. The most common representation of a graph is a diagram, in which the vertices are represented as points and each edge as a line segment joining its end vertices.
Details on the use of graphs may be found in the textbook Graph Theory with Applications to Engineering and Computer Science. Narsingh Deo, Prentice-Hall Publications, 1974.
Directed Acyclic Graph (DAG): A directed graph G consists of a set of vertices V={ν1, ν2 . . . }, a set of edges E={e1, e2 . . . }, and a mapping that maps every edge onto some ordered pair of vertices (vi, vj)].
Shortest Path: In the simplest form, a shortest path is referred to as the path from a given source vertex to a given destination vertex having the least distance (cost).
Depth First Search: As quoted from the aforementioned reference by Narsingh Deo, a depth-first search is a systematic traversal of the edges of a given graph such that every edge is traversed exactly once and each vertex is visited at least once.
Topological Order: The vertices of a directed graph G are said to be in topological order if they are labeled 1, 2, 3, . . . ,n such that every edge in G leads from a smaller numbered vertex to a larger one.
Maximum Flow Problem: Given a network with capacities on edge flows, the maximum flow problem seeks to find a solution to send as much flow as possible between two points in the network while honoring the edge flow capacities. Further details may be found in the textbook “Network Flows: Theory, Algorithms, and Applications”, R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Prentice-Hall Publications, 1993.
Minimum Cost Flow: Given a cost per unit flow on a network edge in addition to edge capacities, the minimum cost flow problem solves for the units of flow to be sent from one point in the network (the source) to one or more points in the network (sink) with minimum cost while honoring the edge flow capacity.
Area Migration: In the context of the present invention, area migration refers to the movement of standard cell area units from one region to another of a VLSI layout.
Manhattan Distance: The distance between two points measured along axes at right angles. In a plane with point p1 at (x1, y1) and point p2 at (x2, y2), the manhattan distance is given by |x1−x2|+|y1−y2|.
The need for placement legalization arises in almost all physical design flows. Several legalization approaches have been adopted in prior works that generally suffer from the following drawbacks: (a) typically use local search heuristics that does not have a global placement view; (b) disturb the given placement (order) significantly leading to inferior placement solution; and (c) do not behave well under difficult instances that have several cell overlaps in the same proximity or fail to legalize under these circumstances.
Among the notable overlap removal methods proposed in the prior art is described in U.S. Pat. No. 5,943,243 which proposes a row level legalization approach, wherein cells are reassigned from over-capacitated regions to free-spaces between fixed-blocks. However, their method attempts a cell-by-cell legalization scheme with restricted local search and does not incorporate a global view of free-space contention, thereby, resulting in large movement of some cells to find a legal placement.
In another approach, described in U.S. Pat. No. 5,619,419, an analytical placement algorithm incorporating overlap removal through repulsive forces to spread cells apart is presented. Such a recursive approach to eliminate cell overlaps is often applied in many top-down placement algorithms but do not lend them for a post-placement legalization scheme.
There also exists some reference to overlap-removal techniques found in the literature, notably: modeling a detailed placement algorithm as a transportation problem which is solved using network flow techniques, as described in the article “Accurate net models for placement improvements by network flow methods,” by K. Doll, F. M. Johannes, and G. Sigl, published in the Proc. IEEE/ACM Int. Conf. on Computer-Aided Design, pp. 594–597, 1992. Although this approach maintains non-overlapping placement, it does not explicitly address placement legalization issues since the input placement is assumed to be overlap-free. In addition, the aforementioned approach does not globally explore the available free-space in the layout area for cell placement assignment. A detailed placement algorithm using a network-flow based approach to migrate cells from overpopulated regions to free-space with minimal perturbation is described in “Algorithms for Detailed Placement of Standard Cells,” Jens Vygen, published in the Proc. of Design Automation and Test in Europe (DATE), pp. 321–324, 1998. However, this modeling restricts the flow (movement) of cells to only the vertical direction across rows of regions and does not account for the horizontal movement of cells while satisfying global capacity and demand constraints. A legalization scheme that uses gain-graph model to ripple move cells to an overlap-free position in the context of detailed placement is presented in “Mongrel: Hybrid Techniques for Standard Cell Placement,” S. Hur and J. Lillis, published in the Proc. IEEE/ACM International Conference on Computer-Aided Design, pp. 165–170, 2000. This method is applicable for resolving single-source overlaps caused by individual cell moves during placement refinement but does not handle multiple regions with overlaps simultaneously.
The approaches presented in the prior art either do not directly address the post-placement legalization problem or they fail to capture the global-view of the problem or they do not account for all the degrees of cell movement in the global-view context. The present invention proposes a two-dimensional model of the given placement instance as a global area migration problem where both horizontal and vertical movement of cells (area units) is effectively captured. Furthermore, efficient techniques to move cells to satisfy the desired area migration across regions with minimal perturbation from the given placement are also disclosed. The proposed approach provides a robust solution to legalize cell placement without compromising on the placement quality.